package com.ljy.my_study.leetcode.累加数;

public class TestMain {

//    累加数 是一个字符串，组成它的数字可以形成累加序列。
//
//    一个有效的 累加序列 必须 至少 包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。
//
//    给你一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。
//
//    说明：累加序列里的数 不会 以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
//
//
//
//    示例 1：
//
//    输入："112358"
//    输出：true
//    解释：累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
//
//    示例 2：
//
//    输入："199100199"
//    输出：true
//    解释：累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
//
//
//
//    提示：
//
//            1 <= num.length <= 35
//    num 仅由数字（0 - 9）组成
//
//
//
//    进阶：你计划如何处理由过大的整数输入导致的溢出?
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/additive-number
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(new TestMain().isAdditiveNumber("198019823962"));
    }

    public boolean isAdditiveNumber(String num) {
        int len=num.length();
        for(int i=1;i<len;i++){
            if(num.charAt(0)=='0'&&i!=1){
                return false;
            }
            long v1=Long.valueOf(num.substring(0,i));
            for(int j=i+1;j<=len;j++){
                if(num.charAt(i)=='0'&&j!=i+1){
                    break;
                }
                long v2=Long.valueOf(num.substring(i,j));
                if(isAdditiveNumber(num,j,v1,v2)){
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isAdditiveNumber(String num,int start,long v1,long v2){
        int len=num.length();
        long v3=v1+v2;
        String s3=String.valueOf(v3);
        int end=start+s3.length();
        if(end>len){
            return false;
        }else if(end==len){
            return num.substring(start,end).equals(s3);
        }
        return isAdditiveNumber(num,end,v2,v3);
    }
}
